Okay, so back to AI.

We started looking at a particular, slightly more interesting piece of search, application

of search technology, which is game playing.

And for certain kinds of games, simple games, board games typically, we can almost directly

use the search algorithms that we talked off in the last weeks.

And I would like to really have you understand this as kind of an application where we take

what we have, search algorithms, and basically teach them a couple new tricks.

Move to a different application area, apply what we have, and see all this stuff where

things break and then fix them.

For some reason.

This is the typical thing.

And already we, chess, go, checkers, tic tac toe, all of these board games, those are the

prime examples I want you to think of.

And already the picture shows us one thing that breaks with respect to our application,

namely we have an opponent, which means we do not control the environment.

The environment is only, you could say, half deterministic.

My actions are deterministic.

They do what I think they should do.

But the environment reacts in the form of the opponent.

And I have no control over that.

And that's exactly the fun.

So that breaks, we're going to use only simple board games.

I've talked about that.

We're going to assume that we have two players, Max and Min, and that we have these terminal

states, the states when the game is over, think of them as goal states, but we have

an additional utility function that tells you how well you did in the game.

For chess it's easy, you win, you lose, or you tie.

For other games it might be more interesting, you win with an advantage of so and so many

pieces or something like this.

Okay, so we talked about not doing soccer, and the first thing that breaks is the notion

of what a solution might be.

In search a solution is a sequence of actions that you control and that bring you from the

initial to the goal states.

That won't work in an environment where you do not control everything.

So what we need here, where we're unsure of what the next state, as Max, we always, that's

one of the conventions, we always talk as if we're Max.

Min is always the opponent, just as a convention.

Nothing hinges on this, it just makes communication easier.

So Max needs a strategy, meaning for all the states that might come back from Min, Max

has to do something.

So a solution here is a strategy.

We want a Max strategy.

And the problem is huge.

Search spaces are huge.

I was not lying when I painted this kind of a search tree.

Here is realistic search trees, 10 to the 50, something like this, states.

And even if you, I don't know, live on a, have an agent that kind of can do gigastate

exploration per second, you're still left with 10 to the 31 states you have, 10 to the

31 seconds.

If you want to compute this in your head, that's longer than you live.